package com.xiaoyu.backtracking;

import java.util.*;

/**
 * @program: DS_and_A
 * @description: 组合总和2
 * 给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 *
 * candidates中的每个数字在每个组合中只能使用一次。
 *
 * 说明：
 *
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。
 * 示例1:
 *
 * 输入: candidates =[10,1,2,7,6,1,5], target =8,
 * 所求解集为:
 * [
 *   [1, 7],
 *   [1, 2, 5],
 *   [2, 6],
 *   [1, 1, 6]
 * ]
 * @author: YuWenYi
 * @create: 2021-05-22 15:48
 **/
public class CombinationSum2_40 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = candidates.length;
        if (len == 0){
            return res;
        }
        //排序是剪枝的基础!
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        //boolean[] used = new boolean[len];  不需要这个used数组也可以解决,如果使用它也可以解决

        dfs(res, path, candidates, target, 0, len);
        return res;
    }
    public void dfs(List<List<Integer>> res,Deque<Integer> path,int[] candidates, int target,int begin,int len){
        if (target == 0){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < len; i++) {
            //if (!used[i]){
                // 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
                if (target - candidates[i] < 0){
                    break;
                }
                //例如是1,2,2,5 那么这个代表的意思就是,既然1号位的2已经递归完成,2号位的2数值和1号位的2数值相同,
                //那么就直接跳过它不进行递归,这称为剪枝,前提是需要对数组排序
                //小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
                /*
                    为什么使用i>begin?
                    在一个for循环中，所有被遍历到的数都是属于一个层级的。我们要让一个层级中，
                    必须出现且只出现一个2，那么就放过第一个出现的2，但不放过后面出现的2。
                    第一个出现的2的特点就是 i == begin. 第二个出现的2 特点是i > begin.
                * */
                if (i > begin && candidates[i] == candidates[i-1]){
                    //System.out.println("被减掉的枝"+path);
                    continue;
                }
                //used[i] = true;
                path.push(candidates[i]);
                //System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));

                // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
                dfs(res, path, candidates, target - candidates[i] , i + 1, len);

                //used[i] = false;
                path.pop();
                //System.out.println("递归之后 => " + path);
            //}
        }
    }


    public static void main(String[] args) {

        CombinationSum2_40 sum40 = new CombinationSum2_40();

        int[] candidates = {10, 1, 2, 7, 6, 1, 5};

        System.out.println(sum40.combinationSum2(candidates, 8));

    }
}
